#ifndef GAMEENGINE_AI_PATH_FINDING_ASTAR_H
#define GAMEENGINE_AI_PATH_FINDING_ASTAR_H

#include <GameEngine/AI/ai_settings.h>

#include <GameEngine/AI/PathFinding/heuristic_default.h>
#include <GameEngine/AI/PathFinding/astar_node.h>

#include <list>
#include <set>



#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif


//! Find the optimal path based on the A-star algorithm
/*!
 *  This algorithm is templated to maximize code usability; hence, the algorithm comes with some
 *  requirements regarding to the classes used in A-star.
 *
 *  <i>The graph class - associated types:</i><br>
 *  1. The graph class should define a Node class that corresponds to some waypoints in the path of
 *     the graph. The node class should come with comparison operators (== and != operators), a copy
 *     constructor, and an assignment operator.<br>
 *  2. The graph class should define a Cost class, typically of numeric type (integer or floating point
 *     numbers). Technically, the Cost class should come with an assignment and an addition operators.
 *
 *  <i>The graph class - methods:</i><br>
 *  1. The graph class should implement a get_children(std::list<Node>& children, Node node) function,
 *     which returns all the nodes connected to the input node, with return value formatted as a STL
 *     list of nodes.<br>
 *  2. The graph class should also implement a cost(Node parent, Node node) function, which returns
 *     the exect cost required to go from the parent to the current node.
 *
 *  <i>The heuristic class - methods:</i><br>
 *  1. The heuristic class should implement a cost(Node start, Node end) const function, which returns
 *     an estimation of the cost to get from the start to the end node. The heuristic will guide the
 *     selection of the nodes in the open list, which can strongly accelerate the research of the
 *     shortest path. Please note that the heuristic MUST NOT overestimate the distance between the
 *     start and the end node (inadmissible heuristic), since this could result in an incorrect
 *     computation of the shortest path. See the explanations of Patrick Lester for more details
 *     about inadmissible heuristics : http://www.policyalmanac.org/games/aStarTutorial.htm <br>
 *     If you cannot get a clue of what the heuristic should be, you can use the HeuristicDefault
 *     class, whose estimated distance is always 0. Please note, however, that this heuristic can
 *     strongly increase the time required to compute the shortest path, since the heuristic does
 *     not favor the most promising nodes.
 */
template <class Graph, class Heuristic = HeuristicDefault<Graph> >
class AStar {

public:
	static bool find_path(  std::list<typename Graph::Node>& res,
							const Graph& graph,
							const typename Graph::Node& start,
							const typename Graph::Node& end,
							bool approximate_path = true);
	static bool find_path(  std::list<typename Graph::Node>& res,
							const Graph& graph,
							const typename Graph::Node& start,
							const typename Graph::Node& end,
							const Heuristic& heuristic,
							bool approximate_path = true);

private:
	typedef std::set< AStarNode<Graph> > AStarList;

private:
	AStar();
	~AStar();

	bool find_path_internal(const Graph& graph, const typename Graph::Node& start, const typename Graph::Node& end, const Heuristic& heuristic);

	bool pick_node(AStarNode<Graph>& res, const typename Graph::Node& end, const Heuristic& heuristic);
	void close_node(const AStarNode<Graph>& node);
	void open_node(const typename Graph::Node& node, const typename Graph::Node& parent, const typename Graph::Cost& cost);
	bool find_close_node(const typename Graph::Node& node, AStarNode<Graph>* astarnode = nil) const;
	bool find_open_node(const typename Graph::Node& node, AStarNode<Graph>* astarnode = nil) const;

private:
	//! The list of nodes that can currently be considered
	AStarList open_list_;

	//! The list of nodes that can have already been considered
	AStarList closed_list_;
};

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#include <GameEngine/AI/PathFinding/astar.hpp>

#endif
